package com.xyz.study.algorithms;

import com.sun.jmx.remote.internal.ArrayQueue;

import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.LinkedBlockingDeque;

/**
 * 树相关算法
 *
 * @author XYZ
 * @version 1.0
 * @since 2021/5/14 17:01
 */
public class TreeAlgorithms {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 前序遍历
     */
    public void preorderTraversal(TreeNode treeNode){
        if (null == treeNode){
            return;
        }
        System.out.println(treeNode.val);
        preorderTraversal(treeNode.left);
        preorderTraversal(treeNode.right);

    }
    /**
     * 中序遍历
     */
    public void inorderTraversal(TreeNode treeNode){
        if (null == treeNode){
            return;
        }
        inorderTraversal(treeNode.left);
        System.out.println(treeNode.val);
        inorderTraversal(treeNode.right);

    }
    /**
     * 后序遍历
     */
    public void postorderTraversal(TreeNode treeNode){
        if (null == treeNode){
            return;
        }
        postorderTraversal(treeNode.left);
        postorderTraversal(treeNode.right);
        System.out.println(treeNode.val);

    }
    /**
     * 层序遍历
     */
    public void levelTraversal(TreeNode treeNode){
        if (null == treeNode){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(treeNode);
        while (!queue.isEmpty()){
            TreeNode queueHead = queue.poll();
            if (null == queueHead) return;
            System.out.println(queueHead.val);
            if (queueHead.left != null){
                queue.add(queueHead.left);
            }
            if (queueHead.right != null){
                queue.add(queueHead.right);
            }
        }

    }
}
